package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 给定一个包含非负整数的 m x n 网格 grid ，
* 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最小路径和_64 {
    public static void main(String[] args) {
        最小路径和_64 demo = new 最小路径和_64();
        int[][] grid = new int[][] {
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        int i = demo.minPathSum1(grid);
        System.out.println(i);
    }

    /*
    * 解题思路： 可以深搜，广搜 也可以动态规划吧
    * 只能向下或者向右
    * */
    private int resultMin = Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        int[][] route = new int[][] {
                {1,0},
                {0,1}
        };
        f(grid,0,0,0,route);
        return resultMin;
    }

    /*
    * i 行 j列 深搜超时 ，考虑动态规划吧
    * */
    public void f(int[][] grid,int i,int j,int now,int[][] route){
        if(i>=grid.length || j>=grid[0].length){
            return;
        }
        now += grid[i][j];
        if(i==grid.length-1 && j == grid[0].length-1){
            // 到达右小角
            resultMin = Math.min(now,resultMin);
            return ;
        }
        // 还未到达 ,向下或者向右
        for(int k=0;k<route.length;k++){
            f(grid,i+route[k][0],j+route[k][1],now,route);
        }
    }

    /*
    * 动态规划
    * */
    public int minPathSum1(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0]; // 第一行第一列 不需要处理
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i==0 && j == 0)
                    continue;
                if(i == 0 && j >0){ // 第一行
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                }else if(j == 0 && i>0){
                    // 第一列
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }else{
                    // 普通的
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                }
            }
        }
       return dp[dp.length-1][dp[0].length-1];

    }
}
